O(n)

O(log n)

h

k

L

f

X f(X)

T f X

Y

m

f ←

˜

X = X

k = 1 . . . , m

f

(k)

= L(

˜

mX)

f ← f

(k)

◦ f

˜

mX ← f

(k)

(

˜

mX)

f ← T (f, X, Y )

f

400

1 4

y

x P (x)

P (y|x) P (x)

P (x) P (y | x)

y x y x

y x

P

1

P

2

P

1

P

2

P

1

P

2

selection switch

x

(1)

x

(2)

x

(3)

h

(3)

h

(2)

h

(1)

y

y x

x

(1)

x

(2)

x

(3)

P

1

P

2

P

1

P

2

(x, y) x

y

x

y

P (x) (x, y)

P (y | x)

X

x

1

x

2

P (x) P (x, y) P (y | x)

−log P (y | x)

−log P (x) −log P (x, y)

P (x) P (y | x)

P (x) P (y | x)

P (x)

x

y x

x y

P (y | x) x P (x)

P (x) P (y | x)

0 5 10 15 20

x

0.0

0.1

0.2

0.3

0.4

0.5

p(x)

y=1 y=2 y=3

Mixture model

x

y

p(x) y

P (x) E[y | x]

x P (y | x)

x

y

P (x)

P (y | x) P (y | x) P(x)

y x

P (x) P (y | x)

y x h

h x

P (h, x) = P (x | h)P (h).

P (x) =



P (x | h)p(h)dh

P (x) =



h

P (x | h)P (h).

x

h

x

y

y

y x

P (y | x) =

P (x | y)P (y)

P (x)

.

P (x) P (y | x)

h y = h

i

h

j

y h

x y P (x | y)

P (y)

P (x | y) P (y)

h P (x | h)

n

2

n

n

n

n

n

n

• k

• k

•

•

•

• n

w

1

w

2

k  n n

O(n

k

)

u ≈ v

f f(u) ≈ f(v)

(x, y) f(x) ≈ y

ˆ

f

n

n

n R

d

d



j=0



n

j



= O(n

d

),

d

f 2

d

O(2

d

)

2

d

n

k

k − 1

d

L n

O





n

d



d(L−1)

n

d



,

L k

O



k

(L−1)+d



.

y = h

i

x

• f x ≈ y

f(x) ≈ f(y)

•

•

• x

P (x)

P (y | x) P (y | x)

P (x)

P (x) P (y | x)

•

y

i

x

f

i

(x) x

y

i

h

P (y

i

| x) P (h | x)

•

•

P (x | = i) i

•

• x

x

•

P (h) =



i

P (h

i

)